package com.liang.leetcode.binarytree.exercise;

import com.liang.leetcode.binarytree.entity.TreeNode;
import com.liang.leetcode.binarytree.util.BiTreeUtil;

import java.util.Arrays;
import java.util.List;

/**
 * 110.平衡二叉树
 */
public class BiTree10_IsBalanced {
    public static void main(String[] args) {
        // 创建一棵完全二叉树
        List<Integer> nodeList = Arrays.asList(1, 2, 2, 3, 3, null, null, 4, 4);
        TreeNode root = BiTreeUtil.createBiTreeByRecursion(nodeList);
        System.out.println("先序遍历：" + BiTreeUtil.preorderTraversal(root));
        // 是否是平衡二叉树
        System.out.println(isBalanced(root));
    }

    // 思路1：先求根节点左右子树的高度，判断高度差是否超过1，超过则返回false，没超过继续递归判断左右子树
    public static boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 求左右子树高度
        int leftDepth = getDepth(root.left);
        int rightDepth = getDepth(root.right);
        if (Math.abs(leftDepth - rightDepth) > 1) {
            return false;
        }
        // 递归判断左右子树
        // return (Math.abs(getDepth(root.left) - getDepth(root.right)) <= 1) && isBalanced(root.left) && isBalanced(root.right);
        return isBalanced(root.left) && isBalanced(root.right);
    }

    public static int getDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = getDepth(root.left);
        int rightDepth = getDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }

}
